/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica5.practica;

import Practica5.structures.Queue;
import Practica5.structures.QueueException;
import Practica5.structures.Stack;
import Practica5.structures.StackException;
import Practica5.util.Graph;
import Practica5.util.Vertex;
import java.io.*;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author miguel
 */
public class BusquedasYRecorridosGraficas {

    public static int BLANCO = 0;
    public static int GRIS = 1;
    public static int NEGRO = 2;

    /**
     * Algoritmo BFS para recorridos en gráficas
     *
     * @param graph Gráfica a la que se le aplicará el recorrido.
     * @param i indice del vértice del que iniciará el recorrido.
     * @return Lista con los vertices ordenados de acuerdo a como fueron
     * visitados.
     * @throws QueueException Excepción si hay algún fallo en la cola.
     */
    public List<Vertex> BFS(Graph graph, int i) throws QueueException, IOException {
        MyGraph g = (MyGraph) graph;
        MyVertex s = (MyVertex) g.getVertex(i);
        for (MyVertex vi : (List<MyVertex>) g.getVertexList()) {
            if (!vi.equals(s)) {
                vi.setColor(BLANCO);
                vi.setDistancia(Integer.MAX_VALUE);
                vi.setPadre(null);
            }
        }
        s.setColor(GRIS);
        s.setDistancia(0);
        s.setPadre(null);
        Queue<MyVertex> Q = new Queue<>();
        BufferedWriter bw = new BufferedWriter(new FileWriter("BFSoutput.txt"));
        String res = "BFS algorithm starting from v"+i+"\n";
        List<MyVertex> myList = new ArrayList<>();
        Q.enqueue(s);
        while (!Q.isEmpty()) {
            MyVertex u = Q.dequeue();
            res += "V"+u.getIndex()+" <Vertex "+u.getIndex()+"> Distance from V"+i+": "+u.getDistancia()+"\n";
            for (MyVertex v : (List<MyVertex>) u.getNeighboursList()) {
                if (v.getColor() == BLANCO) {
                    v.setColor(GRIS);
                    v.setDistancia(u.getDistancia() + 1);
                    v.setPadre(u);
                    Q.enqueue(v);
                }
            }
            u.setColor(NEGRO);
            myList.add(u);
        }
        bw.write(res);
        bw.flush();
        bw.close();
        return (List) myList;
    }

    /**
     * Algoritmo DFS para recorridos en gráficas
     *
     * @param graph Gráfica a la que se le aplicará el recorrido.
     * @param i índice del vertice que iniciará el recorrido
     * @return Lista con los vértices ordenados de acuerdo a como fueron
     * visitados.
     * @throws StackException Excepción si la pila produce algún error.
     */
    public List<Vertex> DFS(Graph graph, int i) throws StackException, IOException {
        MyGraph g = (MyGraph) graph;
        MyVertex s = (MyVertex) g.getVertex(i);
        for (MyVertex vi : (List<MyVertex>) g.getVertexList()) {
            vi.setColor(BLANCO);
            vi.setPadre(null);
        }
        s.setColor(GRIS);
        s.setPadre(null);
        BufferedWriter bw = new BufferedWriter(new FileWriter("DFSoutput.txt"));
        String res = "DFS algorithm starting from: v"+s.getIndex()+"\n";
        Stack<MyVertex> S = new Stack<>();
        List<MyVertex> myList = new ArrayList<>();
        S.push(s);
        int j = 0;
        while (!S.isEmpty()) {
            MyVertex u = S.pop();
            res += "V"+u.getIndex()+" <Vertex "+u.getIndex()+">\tpoped from stack "+(j++)+"\n";
            for (MyVertex v : (List<MyVertex>) u.getNeighboursList()) {
                if (v.getColor() == BLANCO) {
                    v.setColor(GRIS);
                    v.setPadre(u);
                    S.push(v);
                }
            }
            u.setColor(NEGRO);
            myList.add(u);
        }
        bw.write(res);
        bw.flush();
        bw.close();
        return (List) myList;
    }

    public List<Vertex> TopologicalSort(Graph graph, int i) throws StackException,  IOException {
        List<MyVertex> L = new ArrayList<>();
        MyGraph g = (MyGraph) graph;
        MyVertex u = (MyVertex) g.getVertex(i);
        BufferedWriter bw = new BufferedWriter(new FileWriter("Topological-SortOutput.txt"));
        String res = "Topological-sort algorithm, started from: v"+i+"\n";
        while (!g.getVertexList().isEmpty()) {
            L.add(u);
            List<Vertex> X = DFS(g, u.getIndex());
            L.remove(u);
            for(Vertex v: X){
                if(!L.contains((MyVertex)v)){
                    L.add((MyVertex)v);
                }
            }
            for (MyVertex v : L) {
                g.removeVertex(v);
                
            }
            if (!g.getVertexList().isEmpty()) {
                u = (MyVertex) g.getVertexIngradeZero();
                if (u == null) {
                    break;
                }
            }
        }
        int j=0;
        for(Vertex v:L){
            res+= v.getElement()+" <Vertex "+(j++) +"> Label: "+v.getElement()+"\n";
        }
        bw.write(res);
        bw.flush();
        bw.close();
        return (List)L;
    }
}
